/*!
 * \file mcr.h
 *
 * \date Oct 3, 2014
 * \author correa
 */
#ifndef MCR_H_
#define MCR_H_

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#include <graph.h>

/*!
 * \fn int mcr(Graph * g, int * res)
 *
 * \brief Colors input array of vertices according to saturation degree.
 *
 * The specific coloring property: if
 * \f$ c \f$ is the color assigned to a vertex \f$ v \f$ and
 * \f$ \langle v_1, v_2, \ldots, v_i \rangle \f$
 * are the vertices getting color smaller than \f$ c \f$, then \f$ v \f$ is the vertex in the subgraph induced by
 * \f$ V' = \{ v_1, v_2, \ldots, v_i, v \} \f$ with the following properties:
 * -# \f$ deg(v) \geq deg(v_j) \f$, for all \f$ 1 \leq j \leq i \f$;
 * -# if \f$deg(v) = deg(v_j)\f$, then \f$ex-deg(v_j) \leq ex-deg(v)\f$, where \f$ex-deg(u) = \sum_{w \in N(u) \cap V'} deg(w)\f$.
 *
 * This function builds a sequence \f$ \langle v_1, v_2, \ldots, v_r \rangle \f$ of the vertices satisfying the conditions
 * above "from right-to-left": the first vertex to be determined is \f$v_r\f$, then \f$v_{r-1}\f$, and so on.
 *
 * It employs a triple-level priority list described next.
 *
 * A subset of elements \c 0, \c 1, \c ..., \c n \c - \c 1, for a fixed positive integer \c n, is stored according to two levels
 * of priorities. A composition of lists is used in order to perform certain specific operations in (almost) constant time.
 * A general description:
 *
 * \image html triplelist.jpg "Three levels"
 *
 * Levels 1 and 2 implement the two levels of priorities. The elements are stored in the lists of level 3.
 *
 * Nodes in level 1 are sorted by the application, which is usually done according \c key1.
 *
 * Nodes in level 2 are sorted in a decreasing order of \c key2.
 *
 * The lists of levels 1 and 2 are implemented with arrays of fixed size. A list of free nodes is maintained.
 * These three lists share the same nodes, which means that
 * each of such a node is always in one out of three possible states: in the list of level 1, in the list of level 2, or in the
 * list of free nodes.
 *
 * Nodes in level 3 are in an arbitrary order. Two nodes is a same list of level 3 have same \c key2.
 * The value of each node in level 3 is its index in an array of fixed size. For this reason, there is no need for a list of free
 * nodes.
 *
 *
 * Since levels 1 and 2 share their nodes, the following arrays are identified:
 *
 * 	   prev2 = prev1;
 * 	   node1 = key1;
 * 	   first3 = next1;
 *
 * From TripleList:
 *
 * - key1 structural degree of specified vertices in the subgraph induced by them, sorting in descending order
 * - key2 ex-deg of specified vertices in the subgraph induced by them
 *
 * \param g The input graph.
 * \param res New ordering of the vertices.
 *
 * \return The maximum degree in the input graph.
 */
int mcr(Graph * g, int * res);
int heapMcr(Graph * g, int * res);
int decExdegree(Graph * g, int * res);
int decDegree(Graph * g, int * res);

#endif /* MCR_H_ */
